1. Field
Embodiments relate generally to the field of computer graphics.
2. Background
Systems exist for presenting three-dimensional data within a three-dimensional environment. The three-dimensional environment can include a virtual camera that defines what three-dimensional data to display. The virtual camera has a perspective according to its position and orientation. By changing the perspective of the virtual camera, a user can navigate through the three-dimensional environment.
A geographic information system is one type of system that uses a virtual camera to present a three-dimensional environment. A geographic information system is a system for storing, retrieving, manipulating, and displaying a substantially spherical three-dimensional model of, for example, the Earth. The three dimensional model may include satellite images texture mapped to terrain, such as mountains, valleys, and canyons. Further, the three-dimensional model may include both two-dimensional and three-dimensional features that are visible at different zoom levels.
In order to place features at a particular zoom level on a three-dimensional representation of the Earth, geographic information systems need to be able to detect if placing a particular feature will cause an intersection with an already-placed feature. This requires an area search over the surface of a sphere. Traditional solutions for doing this are complex and generally require a significant amount of memory.